package com.breeze.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/contains-duplicate/
 * 217. 存在重复元素
 * 给定一个整数数组，判断是否存在重复元素。
 * <p>
 * 如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
 */
public class LeetCode217 {
    /**
     * 方法一：哈希表
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * <p>
     * 注意：对于一些特定的 n 不太大的测试样例，本方法的运行速度可能会比方法二更慢。这是因为哈希表在维护其属性时有一些开销。要注意，程序的实际运行表现和 Big-O 符号表示可能有所不同。
     * Big-O 只是告诉我们在 充分 大的输入下，算法的相对快慢。
     * 因此，在 n 不够大的情况下， O(n) 的算法也可以比 O(nlogn)的更慢。
     */
    public boolean containsDuplicate(int[] nums) {
        Set set = new HashSet();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            } else {
                set.add(nums[i]);
            }
        }
        return false;
    }

    /**
     * 方法二：排序
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     */
    public boolean containsDuplicate1(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        LeetCode217 leetCode217 = new LeetCode217();
        int[] nums = {1, 2, 3, 1};
        int[] nums1 = {1, 2, 3, 4};
        int[] nums2 = {1, 1, 1, 3, 3, 4, 3, 2, 4, 2};
        System.out.println(leetCode217.containsDuplicate(nums));
        System.out.println(leetCode217.containsDuplicate(nums1));
        System.out.println(leetCode217.containsDuplicate(nums2));

        System.out.println(leetCode217.containsDuplicate1(nums));
        System.out.println(leetCode217.containsDuplicate1(nums1));
        System.out.println(leetCode217.containsDuplicate1(nums2));
    }
}
